実は，この主張は，選択公理と同値になることが示せます (この同値性の証明については，
後で述べます)．
このこと (と選択公理が，選択公理を除いた他の集合論の公理たちから証明できないこと) から，
主張のどんな証明も，完全に構成的なものではあり得ないことがわかります (完全に構成的な証明は，
少なくとも選択公理を除いた他の集合論の公理たちからの証明にはなっているはずだからです)．
次の証明は，
証明で必要になる基本事実と，選択公理を用いる部分を，最初に幾つかの補題として分離することで，
証明の見通しを良くする工夫をしたものです．
次のような記法を用いることにします： $\natnums$ は $0$ も含むものとします．
「自然数 $n$」 と言ったときには，$n=0$ の場合も含めます．
$\{A :\, A$ は $X$ の有限部分集合$\,\}$ を，
$[X]^{<\aleph_0}$ と書くことにします．
また，自然数 $n$ に対して，$\{A :\, A$ は $X$ のちょうど $n$ 個の要素からなる集合$\,\}$ を，
$[X]^n$ と書くことにします (この記法は，
現代の集合論では標準的です．$[X]^0=\ssetof{\emptyset}$ に注意しておきます．)．
$[X]^{<\aleph_0}=\bigcup_{n\in ℕ }[X]^n$ です．集合 $X$ と $Y$ の間に全単射が存在することを，
$X\sim Y$ と書くことにします．また，集合 $X$ が，集合 $Y$ に一対一に埋め込める (つまり，
$X$ から $Y$ への単射が存在する) ことを，$X\hookrightarrow Y$ または，$Y\hookleftarrow
X$ で表わすことにします．
$X$ の$ Y$ への埋め込みが，写像 (単射) $i$ によって実現されているときには，このことを，
$i:X\hookrightarrow Y$ と表わすことにします．
まず，以下の議論で用いることにする基本的な性質を列挙しておくことにします．
次の補題１と定理２はどちらも選択公理なしで証明のできるものです．これらのうち補題１は，
“$\sim$” や “$\hookrightarrow$” の定義や，写像や，逆写像や，写像の合成の基本性質などから，
明らかです．
補題１．(0) すべての集合 $X$, $Y$ について，$X\sim Y$ なら，(a) $Y\sim X$ で，(b) $X\hookrightarrow Y$ である．
(1) すべての集合 $X$, $Y$, $Z$ に対して，$X\hookrightarrow Y$ かつ，$Y\hookrightarrow
Z$ なら，$X\hookrightarrow Z$ である．
(2) すべての集合 $X$, $Y$, $Z$ に対して，$X\sim Y$ かつ，$Y\sim Z$ なら，$X\sim Z$ である．□
次の定理の証明は，少し難しく，自力ではうまく再現することができないかもしれません．
定理２ (Cantor-Schröder-Bernstein の定理)．すべての集合 $X$, $Y$ に対し，$X\hookrightarrow Y$ かつ $Y\hookrightarrow X$ なら，$X\sim Y$ である．□
この定理は，最初の explicit な証明は，実はデデキントが書き下していた，
という，ややこしい歴史を持つ定理で，昔はよく Cantor-Bernstein の定理と呼ばれていたものです．
一番直感的に分かりやすい証明と思われるものは，Martin Aigner, and Günter
Ziegler, Proofs from THE BOOK (4th ed.), Berlin, New York: Springer-Verlag
(2009). にあります ( ただし，この本での証明は formal には正しく書き出せていなくて，
きちんとした証明にするには，若干書き直しが必要に思えるのですが… )．
次の二つの主張の命題は，
それぞれ選択公理 (Axiom of Choice) と同値です．“(AC)” と書き足してあるのは，
選択公理が用いられていることの示唆です．
補題３ (AC)．(1) $\langle A_i:\ i\in I\rangle $, $\langle B_i:\ i\in I\rangle $ を空でない集合の (同じ添字集合 $I$ を持つ) 列とするとき，各 $i\in I$ に対し，$A_i\sim B_i$ なら，$\prod_{i\in I}A_i\ \sim\ \prod_{i\in I}B_i$ である．
(2) $\langle
A_i:\ i\in
I\rangle $, $\langle B_i:\ i\in I\rangle $ が，それぞれ互いに素な集合の列のとき (つまり，
異なる $i,j\in I$ に対し，$A_i\cap A_j=\emptyset, B_i\cap B_j=\emptyset$ が成り立つとき)，
各 $i\in
I$ に対し，
$A_i\sim B_i$ なら，全単射 $h:\,\dot{{\bigcup}}_{i\in I}A_i\ \rightarrow\ \dot{{\bigcup}}_{i\in
I}B_i$ で，$h“A_i=B_i$ が，すべての $i\in I$ に対し成り立つようなものが，存在する．□
上では，$\dot{{\bigcup}}$ と和集合の記号にドットをつけて，
この集合族の和集合が，互いに素な集合たちの和になっていることを表わしています．また，$h“A_i$ は，
集合 $A_i$ の写像 $ h$ による像を表わしています．
補題３の証明は自然にできるので，
気をつけないと，選択公理がフルパワーで使われていることに気がつかないかもしれません．
上の (2) で，
全単射 h の
「$h“A_i=B_i$ が，
すべての $i\in
I$ に対し成り立つ」という性質を落としたときにも主張が選択公理と同値になるかどうかは，
私は知りません．どなたか分かる方がいたら教えていただけないでしょうか？
定理４ (AC)．任意の無限集合 $X$ に対し，$X\sim X^2$ が成り立つ．□
$X^2$ は，
集合 $X$ のそれ自身とのデカルト積 $X\times X$ のことです．同様に， $X$ 自身の $n$個のコピーのデカルト積 $\overbrace{X\times X\times\cdots\times X}^{{ n\ 個}}$ を $X^n$ と書くことにします．
この定理の証明は，少し複雑です．選択公理の下では，任意の無限基数 $\kappa$ に対して，$\kappa\sim\kappa^2$ が成り立つことを証明すれば十分ですが，このことは， (選択公理を用いずに) $\kappa^2$ 上の Gödel ordering と呼ばれる整列順序を用いて，無限基数 $\kappa$ に関する超限帰納法で証明することができます．
定理４の主張も選択公理と同値になることが知られていて，
これは，Tarski の定理 です．Jan Mycielski の A system of axioms of set theory for the rationalists, Notices of the American Mathematical Society, 53(2), 206–213. には，Mycielski が Tarski 自身から聞いた話として，Tarski が，この定理を証明した論文をフランスの Comptes Rendus de l'Académie des Sciences に投稿したところ，フレシェーは「よく知られた命題の間の帰結関係を証明しても新しい結果とは言えない」と言って却下し，ルベーグは「間違った二つの命題の間の帰結関係を証明してもしょうがない」と言って却下したので，Tarski は憤慨して，それ以降この雑誌には論文を投稿しなくなった，という逸話が書かれています．この証明は，例えば，Th. Jech, The Axiom of Choice (1977/2008) の Theorem 11.7 にあります．
この定理と補題１を用いて $n$ に関する帰納法で証明することで，次が得られます：
系５ (AC)．すべての無限集合 $X$ と $n>0$ に対し，$X \sim X^n$ が成り立つ．□
以上の準備をすると，次が証明できるようになります．
補題６ (AC)．すべての無限集合 $X$ と $n>0$ に対し，$X \sim [X]^n$ が成り立つ．
証明． まず，選択公理により， $X$ 上の整列順序 $\sqsubset$ で， $X$ の $\sqsubset$ に関する最大元の存在しないようなものを一つ選んでおく．定理２により，$X \hookrightarrow [X]^n$ と $X \hookleftarrow [X]^n$ を示せば十分である．前者は，埋め込み $g:\,X\rightarrow [X]^n;\ a\mapsto \{a, a^{(1)},a^{(2)},\ldots\,a^{(n-2)}\}$ によりよい．ただし，$a^{(k)}$ で，$a$ の，$ \sqsubset$ に関して，ちょうど $k$個後の要素を表わしている． 後者については，系５により，$X\sim X^n$ だから，補題１ (0), (1) により，$[X]^n\hookrightarrow X^n$ が示せればよい．これは，
$h:\,[X]^n\rightarrow X^n;\ \{a_0,\ldots,a_{n-1}\}\ \mapsto\ \langle a'_0,\ldots,a'_{n-1}\rangle $
によりよい．ただし，上で，$a'_0,\ldots,a'_{n-1}$ は，$a_0,\ldots,a_{n-1}$ の $\sqsubset$ に関する昇順の並べ替えとする．□ (補題６)
補題７ (AC)．$X$ を無限集合とするとき，$X\sim X\times ℕ$ が成り立つ．特に， $X$ の可算無限個の部分集合への分割 $X=\dot{{\bigcup}}_{n\in ℕ }X_i$ で，$X\sim X_n$ が，すべての $n\in ℕ$ に対して成り立つようなものが，存在する．
証明．
選択公理の仮定と，$X$ が無限集合であることから，$ℕ \hookrightarrow X$ が成り立つことに注意する．したがって，一般性を失うことなく，① $ℕ \subseteq X$ と仮定してよい．$f:\,X\rightarrow X\times ℕ ;\ x\mapsto \langle x,0\rangle$ は単射なので，$X\hookrightarrow X\times ℕ$ である．一方，① と，定理２により，$X\times ℕ \subseteq X\times X\sim X $ なので，補題１, (0), (1) により，$X\times ℕ \hookrightarrow X$ が導ける．以上と，定理２により，$X\sim X\times ℕ$ である．
証明の後半は，$g:\,X\rightarrow X\times ℕ$ を全単射として，$X_n:=g^{-1}“X\times\{n\}$, $n\in ℕ$ とすれば，これが求めるものである．
ただし，$g^{-1}“X\times\{n\}$ で，集合 $X\times\{n\}$ の $g$ による逆像を表わしている．
□ (補題7)
以上の準備から，質問の主張の証明ができることになります．ここでは，見かけ上， 質問の主張より強い，次の定理を証明することにします．
定理８．$X$ を任意の無限集合とするとき，$X\sim[X]^{<\aleph_0}$ が成り立つ．
証明．補題７により，$X$ の可算無限個の部分集合への分割 $X=\dot{{\bigcup}}_{n\in ℕ }X_n$ で，$X\sim X_n$ がすべての $n\in ℕ$ に対して成り立つようなものがとれる．この分割に手を加えて，$X_0$ は singeton で，すべての $n>0$ に対しては，$X_n\sim X$ となるように変更する．このとき，補題６ (と補題１,(2)) により，各 $n\in ℕ$ に対し，$X_n\sim [X]^n$ となる ( $[X]^0=\{\emptyset\}$ となることに注意)．したがって，補題３, (2) により，
$X=\dot{{\bigcup}}_{n\in ℕ}X_n\ \sim\ \dot{{\bigcup}}_{n\in ℕ}[X]^n=[X]^{<\aleph_0}$
である．このことと，補題１, (2) により，$X\sim [X]^{\aleph_0}$ が導かれる．□ (定理８)
最後に，定理８の主張 (あるいは質問での主張) から選択公理が導かれることを注意しておきます． これは，次のようにして見ることができます： 定理８の主張 (あるいは質問での主張) から， 補題６の命題の $n=2$ の場合:
(*) すべての無限集合 $X$ に対し，$X\sim[X]^2$ が成り立つ
を導くことができますが，定理４の後で触れた Jech の本にある証明に手を加えると， (*) と選択公理が同値になることの証明が，得られます．